1. Field of the Invention
The invention relates to planning maneuvers of one or more actors (machines or people), where movement is possible in at least two dimensions, and is subject to two independent space-variant constraints or scenarios. In particular, the invention is applicable to planning travel, for example through time or space, where a rendezvous is required between one actor and another actor or condition which is also moving through the time or space.
The most common application for path planning has been for controlling robots. In the typical robot path plan, a path is chosen to get the robot (or a portion of it, such as a gripping member) from a start point to a goal point while avoiding obstacles. Computer simulation/control has been one of the great advances in improving performance, particularly in multidimensional situations.
Other applications of the invention may lie in traffic or emergency vehicle controls or planning or predicting possible routes or activities of people or machines in dynamic situations.
2. Description of the Prior Art
The related applications listed above form a background to the invention. These applications disclose, among other things, propagating cost waves through a configuration space by budding, using a space-variant metric. In simple path-planning problems, the configuration space represents a two-dimensional physical condition which has been discretized. Using a typical rectangular coordinate system, each configuration state then represents a task state or physical condition which is described by various parameters having known values. A list of these values in a specific order, known as a tuple, describes each configuration state. The configuration space, then, covers or is the span of the tuples.
Goal locations or states are defined, and are fixed for a set of analyses. Selection of a starting position is one step of the planning method.
The cost of transition from one configuration state to another, known as a cost metric but also referred to herein simply as a metric, is defined for each configuration state in a configuration space, with respect to each of its neighbors. Where it is impossible or highly undesirable for an actor (e.g., a machine) to be in a particular configuration state, that state is considered an obstacle. Movement into that state may then be associated with a very high, or infinite, transition cost. The neighborhood may then be defined as including only those states whose transition cost is undefined, or has a finite value--that is, a permissible state change.
Budding starts at a source, usually the goal or goals in a given configuration space, and is used to generate a direction arrow and a cost-to-goal metric for each state, in a wave of calculations expanding from the goal. A graphical view of this expansion process gives rise to the term "cost wave propagation." The direction arrows generated for each configuration space point back to the lowest cost path to the goal. In control processes for robots, this has the advantage that, in the event that the robot has deviated from the optimum path, identification of the state it is in immediately makes the new best path direction known.
A specific improvement to the budding process, described in U.S. Pat. No. 4,949,277, involves differential budding of only a small part of the configuration space when, for example, an obstacle or goal is added to, moved a small distance in, or removed from that space.
U.S. Pat. No. 5,083,256, a continuation-in-part of Ser. No. 166,599 referred to above, discloses a variation of differential budding which takes into account changes in transitions in a configuration space, rather than just changes in the states themselves.